// Aloudin (Albert) Akhriev, 1998-2000.

#ifndef ALIB_ALGORITHM_H
#define ALIB_ALGORITHM_H

////////////////////////////////////////////////////////////////////////////
// F U N C T I O N S:
////////////////////////////////////////////////////////////////////////////
//
// ITER max_fabs_element(ITER F, ITER L)
// ITER min_fabs_element(ITER F, ITER L)
//
// OI copy(II srcF, II srcL, OI dstF, OI dstL)
// OI copy(II srcF, II srcL, OI dstF, OI dstL, unsigned srcInc, unsigned dstInc)
// OI copy_convert(II srcF, II srcL, OI dstF, OI dstL)
//
// void add(IT F, IT L, ITEM i)
// void multiply(IT F, IT L, MULTIPLIER m)
// void module(ITER F, ITER L)
//
// void moment0(I f, I l, A a)
// void moment1(I f, I l, A a)
// void moment2(I f, I l, A a)
//
////////////////////////////////////////////////////////////////////////////

namespace xtd
{

//--------------------------------------------------------------------------
// Return iterator of element with maximal absolute value (or L for empty
// sequence). N O T E: Use function for float-point digit array only.
//--------------------------------------------------------------------------
template<class ITER> inline
ITER max_fabs_element(ITER F, ITER L)
{
  ITER it = F;
  if (F != L)
  {
    double max = fabs(*F);
    while(++F != L)
    {
      double t = fabs(*F);
      if (max < t)
      {
        max = t;
        it = F;
      }
    }
  }
  return (it);
}


//--------------------------------------------------------------------------
// Return iterator of element with minimal absolute value (or L for empty
// sequence). N O T E: Use function for float-point digit array only.
//--------------------------------------------------------------------------
template<class ITER> inline
ITER min_fabs_element(ITER F, ITER L)
{
  ITER it = F;
  if (F != L)
  {
    double min = fabs(*F);
    while(++F != L)
    {
      double t = fabs(*F);
      if (min > t)
      {
        min = t;
        it = F;
      }
    }
  }
  return (it);
}


template<class II, class OI>
OI copy(II srcF, II srcL, OI dstF, OI dstL)
{
  assert(std::distance(srcF,srcL) == std::distance(dstF,dstL));
  dstL = dstF;               // prevent warning
  while(srcF != srcL)
  {
    *dstF = *srcF;
    dstF++;
    srcF++;
  }
  return (dstF); 
}


template<class II, class OI>
OI copy(II srcF, II srcL, OI dstF, OI dstL, unsigned srcInc, unsigned dstInc)
{
  assert(std::distance(srcF,srcL)/srcInc == std::distance(dstF,dstL)/dstInc);
  dstL = dstF;               // prevent warning
  while(srcF != srcL)
  {
    *dstF = *srcF;
    dstF += dstInc;
    srcF += srcInc;
  }
  return (dstF); 
}


template<class II, class OI, class SOURCE_TYPE, class RESULT_TYPE>
OI copy_convert(II srcF, II srcL, OI dstF, OI dstL)
{
  assert(std::distance(srcF,srcL) == std::distance(dstF,dstL));
  dstL = dstF;               // prevent warning
  while(srcF != srcL)
  {
    *dstF = (RESULT_TYPE)((SOURCE_TYPE)(*srcF));
    dstF++;
    srcF++;
  }
  return (dstF); 
}


template<class ITER, class ITEM>
void add(ITER F, ITER L, ITEM i)
{
  for(; F != L; ++F)
    (*F) += i;
}

template<class ITER, class MULTIPLIER>
void multiply(ITER F, ITER L, MULTIPLIER m)
{
  for(; F != L; ++F)
    (*F) *= m;
}

template <class I, class A>
A moment0(I f, I l, A a)
{
  for(; f != l; ++f)
    a += *f;
  return a;
}

template <class I, class A>
A moment1(I f, I l, A a)
{
  int x = 0;
  for(; f != l; ++f, ++x)
    a += *f * x;
  return a;
}

template <class I, class A>
A moment2(I f, I l, A a)
{
  int x = 0;
  for(; f != l; ++f, ++x)
    a += *f * (x*x);
  return a;
}

template<class ITER>
void module(ITER F, ITER L)
{
  for(; F != L; ++F)
    (*F) = ((*F) >= 0) ? (*F) : -(*F);
}


//--------------------------------------------------------------------------
// Searches an ascendantly sorted sequence for the given value.
//--------------------------------------------------------------------------
template<class ITER, class TYPE>
ITER find_ascendant_sorted(ITER first, ITER last, const TYPE & value)
{
  ITER lo = first, hi = last, it = last;

  while(lo < hi)
  { 
    it = lo + (hi - lo) / 2;
    if ((*it) == value)
    {
      return it;
    }
    else if ((*it) > value)
    {
      lo = it + 1;
    }
    else // ((*it) < value)
    {
      hi = it;
    }
  }
  return last;
}


//--------------------------------------------------------------------------
// Searches a sorted sequence for given value
//--------------------------------------------------------------------------
template<class ITER, class CMP>
ITER find_sorted(ITER first, ITER last, CMP cmp)
{
  ITER lo = first, hi = last, it = last;

  while(lo < hi)
  { 
    it = lo + (hi - lo) / 2;
    int code = cmp(*it);

    if (code == 0)
    {
      return it;
    }
    else if (code > 0)
    {
      lo = it + 1;
    }
    else // (code < 0)
    {
      hi = it;
    }
  }
  return last;
}

} // namespace xtd

#endif  // ALIB_ALGORITHM_H
